package cn.xuchunh;

public class MergeSort {
    public static void sort(int[] source, int start, int end) {
        if(source == null || source.length == 0) {
            return;
        }

        if(start >= end) {
            return;
        }

        int mid = (start + end) / 2;
        int start1  = start;
        int end1 = mid;
        int start2 = mid + 1;
        int end2 = end;
        sort(source, start1, end1);
        sort(source, start2, end2);

        //merge
        int[] temp = new int[source.length];
        int index = start;
        while (start1 <= end1 && start2 <= end2) {
            temp[index++] = source[start1] < source[start2] ? source[start1++] : source[start2++];
        }
        while (start1 <= end1) {
            temp[index++] = source[start1++];
        }
        while (start2 <= end2) {
            temp[index++] = source[start2++];
        }
        for (int i = start; i < end + 1; i++) {
            source[i] = temp[i];
        }
    }

    //非递归实现
    public static void sort2(int[] source) {
        if(source == null || source.length == 0) {
            return;
        }

        int window = 1;
        int[] temp = new int[source.length];
        int index = 0;
        for(; window <= source.length; window *= 2) {
            for (int start = 0; start < source.length; start += 2 * window) {
                int start1 = start;
                int end1 = (start + window) > source.length ? source.length : start + window;
                int start2 = end1;
                int end2 = (start + 2 * window) > source.length ? source.length : start + 2 * window;

                index = start1;
                while (start1 < end1 && start2 < end2) {
                    temp[index++] = source[start1] < source[start2] ? source[start1++] : source[start2++];
                }
                while (start1 < end1) {
                    temp[index++] = source[start1++];
                }
                while (start2 < end2) {
                    temp[index++] = source[start2++];
                }
                for (int i = start; i < end2; i++) {
                    source[i] = temp[i];
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] array = new int[]{3,4,53,5621,52,52,52,542,16,6513,5,163,561,165,163,165,165};
        sort(array, 0, array.length - 1);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + ", ");
        }

        System.out.println();
        sort2(array);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + ", ");
        }
    }
}
